Encrypted databases provide data protection (security) in cloud platforms and/or database-as-a-service settings. In encrypted databases, data can be encrypted at the client and can be provided to the database for storage. In some examples, the encryption keys are exclusively stored at the client, and queries (operations) to the database are performed over encrypted data.
To execute some queries, e.g., queries including joins, proxy re-encryption (PRE) can be performed, which translates a ciphertext under one key to a ciphertext under another key without knowing either of the keys. Using PRE, the client issues a PRE key to the database. The database uses the PRE key to re-encrypt at least one column involved in the join operation, such that multiple columns in the join operation are encrypted under the same key. This can be referred to as dynamically adjusting the database encryption.
One reason for dynamically adjusting the database encryption to the queries is that PRE can reveal information to an attacker that is observing the database. For example, the attacker could obtain ciphertexts, and that can be used in cryptanalysis of the keys. When the database receives the PRE key, the database chooses a column which to re-encrypt, and chooses the column under an unknown schedule of future operations, e.g. future joins. Naive approaches to column selection can lead to an infinite number of re-encryptions.